package primary.code07_Greedy;

import java.util.PriorityQueue;

/**
 * @author Yudi Wang
 * @date 2021/8/9 14:32
 * <p>
 * 从一个不断输入的数据流中获取中位数
 */
public class Code06_Median {

    //小于中位数的一半（大根堆）
    private static PriorityQueue<Integer> lowHalf = new PriorityQueue<>(((o1, o2) -> o2 - o1));

    //大于中位数的一半（小根堆）
    private static PriorityQueue<Integer> highHalf = new PriorityQueue<>();

    /**
     * 数据流添加一个数
     *
     * @param num
     * @return
     */
    private static void add(int num) {
        //放入左边
        if (lowHalf.isEmpty() || num <= lowHalf.peek()) {
            lowHalf.add(num);
        } else {
            highHalf.add(num);
        }
        //判断是否需要调整两边
        if (Math.abs(lowHalf.size() - highHalf.size()) > 1) {
            if (lowHalf.size() > highHalf.size()) {
                highHalf.add(lowHalf.poll());
            } else {
                lowHalf.add(highHalf.poll());
            }
        }
    }

    /**
     * 思路：
     * 设计一个大根堆，一个小根堆（意为小于等于中位置数，大于中位数）
     * 检查添加的数
     *
     *
     */
    private static void addTest(int num) {
        if (lowHalf.isEmpty() || num <= lowHalf.peek()) {
            lowHalf.add(num);
        } else {
            highHalf.add(num);
        }
        if (Math.abs(lowHalf.size() - highHalf.size()) <= 1) return;
        if (lowHalf.size() > highHalf.size()) {
            highHalf.add(lowHalf.poll());
        } else {
            lowHalf.add(highHalf.poll());
        }
    }

    /**
     * 返回数据流的中位数
     *
     * @return
     */
    private static int get() {
        if (lowHalf.size() < highHalf.size()) {
            return highHalf.peek();
        } else {
            return lowHalf.peek();
        }
    }

    private static int getTest() {
        if (lowHalf.size() > highHalf.size()) {
            return lowHalf.peek();
        } else {
            return highHalf.peek();
        }
    }

    //当前中位数：1
    //当前中位数：1
    //当前中位数：2
    //当前中位数：2
    //当前中位数：3
    //当前中位数：3
    //当前中位数：4
    //当前中位数：4
    //当前中位数：5
    //当前中位数：5
    public static void main(String[] args) {
//        add(1);
//        System.out.println("当前中位数：" + get());
//        add(2);
//        System.out.println("当前中位数：" + get());
//        add(3);
//        System.out.println("当前中位数：" + get());
//        add(4);
//        System.out.println("当前中位数：" + get());
//        add(5);
//        System.out.println("当前中位数：" + get());
//        add(6);
//        System.out.println("当前中位数：" + get());
//        add(7);
//        System.out.println("当前中位数：" + get());
//        add(8);
//        System.out.println("当前中位数：" + get());
//        add(9);
//        System.out.println("当前中位数：" + get());
//        add(10);
//        System.out.println("当前中位数：" + get());
        addTest(1);
        System.out.println("当前中位数：" + getTest());
        addTest(2);
        System.out.println("当前中位数：" + getTest());
        addTest(3);
        System.out.println("当前中位数：" + getTest());
        addTest(4);
        System.out.println("当前中位数：" + getTest());
        addTest(5);
        System.out.println("当前中位数：" + getTest());
        addTest(6);
        System.out.println("当前中位数：" + getTest());
        addTest(7);
        System.out.println("当前中位数：" + getTest());
        addTest(8);
        System.out.println("当前中位数：" + getTest());
        addTest(9);
        System.out.println("当前中位数：" + getTest());
        addTest(10);
        System.out.println("当前中位数：" + getTest());
    }
}
